package me.timlong.StringDynamic;

public class MaxPanlinDrome {

    /**
     * 题目描述:
     * 找出给出的字符串S中最长的回文子串。假设S的最大长度为1000，并且只存在唯一解。
     *
     * 解决方案：
     *
     * 考虑使用f(i, j)，其中 0 <= i <= j  < s.length 表示s[i...j]是否为回文数
     * 记录当前获得的最大的回文串长度 maxLen，
     * 为了减少计算应该在新的遍历的基础上排除小于目前最大长度的回文串判断
     *
     */
    public String longestPalindrome(String s) {

        if(null == s || s.length() == 1)
            return s;

        int sLen = s.length();
        String panlindrome = "";

        for (int i = 0; i < sLen; i++)
            for (int j = i; j < sLen; j++) {
                if(j - i + 1 < panlindrome.length())
                    continue;
                if(isPanlindrome(s.substring(i, j + 1)))
                    panlindrome = s.substring(i, j + 1);
            }
        return panlindrome;
    }

    private boolean isPanlindrome(String str){

        char[] chars= str.toCharArray();

        int i = 0;
        int j = str.length() - 1;

        while(i < j){
            if(chars[i] == chars[j]){
                i++;
                j--;
            } else
                return false;
        }
        return true;
    }

    /**
     * 高效算法: 考虑两种情况回文串的中间节点为“bab”与“aa”两种情况
     * 对字符串进行一次遍历，时间复杂度为O(n)
     */
    public String longestPalindrome2(String s) {

        if(null == s || s.length() == 1)
            return s;

        String result = "";
        int maxPanlindromeLen = Integer.MIN_VALUE;
        for (int i = 0; i < s.length() - 1; i++) {
            String resultEven = findMaxPanlindrome(s, i, i + 1);
            String resultOdd = findMaxPanlindrome(s, i, i);

            resultEven = resultEven.length() < resultOdd.length() ? resultOdd : resultEven;
            result = result.length() < resultEven.length() ? resultEven : result;
        }

        return result;
    }

    private String findMaxPanlindrome(String str, int i, int j){

        while(i >= 0 && j < str.length() &&
                str.charAt(i) == str.charAt(j)) {
            i--;
            j++;
        }
        return str.substring(i + 1, j);
    }

    public static void main(String[] args) {
        String str = "0bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb110fjakjfaaaaabbaaaaa";
        String s = "4444";
        System.out.println(new MaxPanlinDrome().longestPalindrome2(str));

    }

}
